package com.tgy.leetcode;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * @Author: tgy
 * @Date: 12/5/20 11:22 AM
 *
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 */
public class _297_二叉树的序列化与反序列化_02 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        if (root == null) {

            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        TreeNode node = null;
        while (!queue.isEmpty()) {

            node = queue.poll();

            if (node == null) {

                sb.append("null,");
                continue;
            }

            queue.offer(node.left);
            queue.offer(node.right);
            sb.append(node.val).append(",");
        }

        if (sb.charAt(sb.length() - 1) == ','){

            sb.deleteCharAt(sb.length() - 1);
        }

        sb.append("]");
        return sb.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if (data == null || !data.startsWith("[") || !data.endsWith("]")) {

            return null;
        }

        data = data.substring(1,data.length() - 1);

        if (data.length() == 0) {

            return null;
        }

        String[] nodeVals = data.split(",");

        TreeNode root = new TreeNode(Integer.parseInt(nodeVals[0]));

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int index = 1;
        TreeNode node = null;
        while (!queue.isEmpty()) {

            node = queue.poll();

            if (index >= nodeVals.length) {
                break;
            }

            if (!nodeVals[index].equals("null")) {

                node.left = new TreeNode(Integer.parseInt(nodeVals[index]));
                queue.offer(node.left);

            }
            index++;

            if (index >= nodeVals.length) {
                break;
            }

            if (!nodeVals[index].equals("null")) {

                node.right = new TreeNode(Integer.parseInt(nodeVals[index]));
                queue.offer(node.right);
            }

            index++;
        }

        return root;
    }
}
